The present invention concerns optimal partitioning of circuit components into an unspecified number of clusters such that the number of inter-cluster connections is minimal.
In the design of integrated circuits, circuitry consists of functional blocks of logic often called components, which are interconnected by connection lines. When laying out the circuitry on one or more integrated circuits it is often desirable to cluster the components together. When clustering the components it is important to minimize the interconnections between clusters. This is because interconnections between components require the placement of connection lines. Connection lines have a measurable width and take up space on the integrated circuit which is directly proportional to their length. On a single integrated circuit, interconnections between clusters generally require connections lines which are on average longer than connection lines which are used for connections within clusters. Therefore, minimizing the interconnections between clusters reduces the amount of surface area of an integrated circuit required by the circuitry.
In the prior art, the clustering of components has generally been done using one of two methods. The first method includes the use of repetitive bi-partitioning. For further explanation of this method, see for example B.W. Kernighan and S. Lin; An Efficient Heuristic Procedure for Partitioning Graphs; Bell System Technical Journal; 49(2):291-307; February 1970. The second method includes the cluster growth around seed components. For further explanation of this method, see for example H. Cho, G. Hachtel, M. Nach, and L. Setiono; BEAT NP: A tool for Partitioning Boolean Networks; Proceedings of the ICCAD, pp. 10-13; November 1988.
The above-discussed prior art methods depend on arbitrary decisions. For example, in the first method which uses repetitive bi-partitioning, arbitrary decisions are made about the size of the partitions, e.g., typically the partitions are assumed to be of equal size. In the second method which uses cluster growth around seed components, arbitrary decisions are made about the choice of seed components. In either case, different choices can lead to completely different results. It is desirable, therefore, to employ a method which does not rely on arbitrary decisions to arrive at an optimal partitioning of circuit components into clusters.